UVa/10664 - Luggage/10664.cpp

   1 #include <iostream>
   2 #include <cassert>
   3 #include <sstream>
   4 #include <string>
   5 #include <vector>
   6
   7 using namespace std;
   8
   9 const int MAXSUM = 200;
  10 const int MAXCOINS = 20;
  11 //dp[i][j] = verdadero si puedo repartir las primeras i monedas en dos grupos que difieran en j
  12 bool dp[MAXCOINS][MAXSUM+1];
  13
  14 int main(){
  15   int runs;
  16   string s;
  17   cin >> runs;
  18   getline(cin, s);
  19   while (runs--){
  20     memset(dp, false, sizeof dp);
  21     getline(cin, s);
  22     stringstream sin(s);
  23     int n, x, sum;
  24     n = sum = 0;
  25     vector<int> m;
  26     while (sin >> x){
  27       ++n, m.push_back(x), sum += x;
  28     }
  29     assert(n == m.size());
  30
  31     dp[0][m[0]] = true;
  32     for (int i=1; i<n; ++i){
  33       for (int j=0; j<=sum; ++j){
  34         dp[i][j] = dp[i-1][abs(j - m[i])];
  35         if (j + m[i] <= sum){
  36           dp[i][j] |= dp[i-1][j + m[i]];
  37         }
  38       }
  39     }
  40     cout << (dp[n-1][0]?"YES":"NO") << endl;
  41   }
  42   return 0;
  43 }
  44